package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// 1302. 层数最深叶子节点的和
// 给你一棵二叉树的根节点 root ，请你返回 层数最深的叶子节点的和 。

// 层序 遍历，找到最后一层的和
// 具体：每一层都算和

func deepestLeavesSum(root *TreeNode) int {
	if root == nil {
		return 0
	}
	var sum int
	var queue []*TreeNode
	queue = append(queue, root)

	for len(queue) > 0 {
		// 遍历下一层
		var curNode *TreeNode
		var curSum int
		var curLen int = len(queue)
		for i := 0; i < curLen; i++ {
			curNode = queue[0]
			queue = queue[1:]
			curSum += curNode.Val
			// 子节点入
			if curNode.Left != nil {
				queue = append(queue, curNode.Left)
			}
			if curNode.Right != nil {
				queue = append(queue, curNode.Right)
			}
		}
		// 如何判断是最后一层？
		// 或者不用判断
		sum = curSum
	}
	// 跳出循环，则sum保存的是最后一次的值
	return sum
}


func main() {

}